
<html>
<head>
	<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
	<link rel=stylesheet href='include/hoj.css' type='text/css'>
</head>
<body>
<center>
<div style="width:90%; text-align:left">
<img src="image/logo.png"/>
</div>
<table width=96%> 
	<tr align="center" class='hd' valign="top">
				<th><a href="faqs.php">F.A.Qs</a></th>
		<th><a href="./bbs.php">Web Board</a></th>
		<th><a href="./">Home</a></th>
		<th><a href="./problemset.html">ProblemSet</a></th>
		<th><a href="./status.php">Status</a></th>
		<th><a href="./ranklist.php">Ranklist</a></th>
		<th><a href="./contest.php">Contest</a></th>
		<th><a href=loginpage.php>Login</a></th><th><a href=registerpage.php>Register</a></th>	</tr>
</table>
</center>
<center>
<div class="notice">
	<div>
		<B>Notice:</B>鉴于种种原因，本OJ自下周星期一（3月5号）开始不再全面开放，请各位做好善后事宜，谢谢合作。	</div>
</div>
</center>
</div>
<title>Problem 2053. -- SRM199 ClosestPoints -- 衡阳八中OJ离线版-2012-02-29</title><center><h2>2053: SRM199 ClosestPoints</h2><span class=green>Time Limit: </span>10 Sec&nbsp;&nbsp;<span class=green>Memory Limit: </span>64 MB<br><span class=green>Submit: </span>51&nbsp;&nbsp;<span class=green>Solved: </span>12<br>[<a href='submitpage.php?id=2053'>Submit</a>][<a href='problemstatus.php?id=2053'>Status</a>][<a href='bbs.php?id=2053'>Discuss</a>]</center><h2>Description</h2><div class=content><p>NOTE: This problem statement contains subscripts and superscripts which may not display properly for plugin users. Write a program to generate a list of random 3D points in space, and then compute the distance between the pair of closest points. Also determine how many distinct pairs of points are this exact distance apart. Generate the random points using the following pseudo-random number generator. Starting with a given seed0: seedi+1 = (seedi * 16807) mod (231-1) The ith random number (starting at i = 1) is given by: randi = (seedi mod (2 * range)) - range The 3D points are triples of 3 successive random numbers: (rand1, rand2, rand3) (rand4, rand5, rand6) (rand7, rand8, rand9) (rand10, rand11, rand12) etc... You will be given an initial seed, the range, and N (the number of points). The random numbers produced by the generator will be between -range and range-1, inclusive. Return a int[] with two elements: the first element should be the square of the distance between the pair of closest points, and the second element should be the number of distinct pairs of points that have this same squared distance. NOTE: Be sure to use 64-bit arithmetic for the multiply and mod in the random-number generator, and for computing squared distances. 给出N，Range，Seed0，按照Seedi+1 = (Seedi * 16807) mod (231-1)以及Randi = (Seedi mod (2 * Range)) &ndash; Range的规则，计算出Rand1 到Rand3n 。定义三维空间内的点Pk的坐标为（Rand3k-2, Rand3k-1, Rand3k）{1&le;k&le;n}。求出所有点中两点间最小距离的平方以及有多少对点的距离等于最小距离。 2 &le; N &le; 150000，1 &le; Range &le; 10^6，1 &le; Seed &le; 10^3 Definition Class: ClosestPoints Method: distance Parameters: int, int, int Returns: int[] Method signature: int[] distance(int N, int range, int seed) (be sure your method is public) Notes - Ignore any duplicate points. (See example 1.) - There will be at least 2 unique points. Constraints - N will be between 2 and 150000, inclusive. - range will be between 1 and 1000000, inclusive. - seed will be between 1 and 1000, inclusive. - The square of the distance of the closest pair of points will be less than 1000000000.</p>
<p>注意:如果有多个点重合，就当成一个点</p></div><h2>Input</h2><div class=content></div><h2>Output</h2><div class=content></div><h2>Sample Input</h2>
			<div class=content><span class=sampledata>3<br />
100<br />
1<br />
 <br />
</span></div><h2>Sample Output</h2>
			<div class=content><span class=sampledata>9163<br />
1<br />
</span></div><h2>HINT</h2>
			<div class=content><p><p>The three points are: (-93, -51, -27), (-42, 30, -28), and (44, -22, 23). The closest pair of points are the first and third, and the square of their distance is 9163. There is 1 pair of points with a squared distance of 9163.</p></p></div><h2>Source</h2>
			<div class=content><p><a href='problemset.html?search=三维最近点对'>三维最近点对</a></p></div><center>[<a href='submitpage.php?id=2053'>Submit</a>][<a href='problemstatus.php?id=2053'>Status</a>][<a href='bbs.php?id=2053'>Discuss</a>]</center>﻿<br>

<a href="./"><span class=red>HOME</span></a>
<a href="javascript:history.go(-1)"><span class=red>Back</span></a>

<hr>
<center>
	<div class="footer">
			<a href=setlang.php?lang=ko>한국어</a>&nbsp;
		<a href=setlang.php?lang=cn>中文</a>&nbsp;
		<a href=setlang.php?lang=fa>فارسی</a>&nbsp;
		<a href=setlang.php?lang=en>English</a>&nbsp;
		<a href=setlang.php?lang=th>ไทย</a>
	<br>		<div>版权所有 &copy;2008-2012 WaterPark Organization. | <script src="http://s21.cnzz.com/stat.php?id=2982771&web_id=2982771" language="JavaScript"></script>
</div>
		<div>Based on opensource project <a href="http://hustoj.googlecode.com">hustoj</a>.</div>
	</div>
</center>
</body>
</html>
